﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

public class Solution198
{
    public int Rob(int[] nums)
    {

        if (nums.Length == 1)
        {
            return nums[0];
        }

      
        int[] dp= new int[nums.Length];//当前房间偷的
        dp[0] = nums[0];
        dp[1] = Math.Max(nums[0], nums[1]);
        
        for (int i=2; i<nums.Length; i++)
        {


            //上一间偷的，这一间不偷，dp[i]=dp[i-1]
            //上一间不偷，这一间偷不偷都行，dp[i]=dp[i-2]+nums[i]
            dp[i] = Math.Max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[nums.Length-1];


    }
}
class Program198
{
    static void Main198(string[] args)
    {

        Solution198 solution198 = new Solution198();
        int[] nums = [1, 2, 3, 1];
      int res=  solution198.Rob(nums);
        Console.WriteLine(res);
        Console.WriteLine("123"+"dwd");
    }
}